package Algorithm.dynamicProgramming.swordOffer;

/**
 * 剑指 Offer 42. 连续子数组的最大和 https://leetcode.cn/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof
 * 题目简述：给定一个整数数组，数组中的一个或连续多个整数组成一个子数组。求总和最大的子数组的和值
 */
public class MaxSubArray {

    /**
     * 1. 定义dp[i]: 以nums[i]结尾的子数组最大和
     * 2. 确定递推公式：dp[i] = dp[i-1] > 0 ? dp[i-1] + nums[i] : nums[i];
     * 3. 初始化：dp[0] = nums[0];
     * 4. 开始遍历：从头遍历至尾
     */
    public int maxSubArray(int[] nums) {
        int dpi = -1, max = nums[0];
        for (int n : nums) {
            dpi = dpi > 0 ? dpi + n : n;
            max = Math.max(max, dpi);
        }
        return max;
    }
}
